With the introduction of new switching technologies in recent years, it is no longer necessary for telephone traffic (or voice and data traffic on an integrated network) to be routed along a fixed origin-destination route. One of the early steps towards more flexible routing was the introduction of automatic alternative routing, which allows traffic on overloaded direct routes to be diverted via alternative, pre-assigned routes. The introduction of stored program controlled (SPC) exchanges and common channel signalling have opened up the possibility of increased flexibility.
A number of routing strategies have been put forward. In a strategy proposed by Bell-Northern Research, calls are routed directly if possible; if not they are routed on an alternative two link path recommended by a central processor. The central processor chooses the recommended path probabilistically with a probability proportional to the number of free circuits on each route after subtracting a reserved number of circuits (a trunk reservation parameter). Each exchange is linked to the central processor and transmits data on availability to the central processor every 5 to 10 seconds. For large networks, the amount of information received by the central processor each 5-10 second period is large. The central processor decides on alternative routes for calls on the basis of information gathered on average about 5 seconds ago.
Another similar system, proposed by Forestier and Lottin, avoids the use of a central processor. Exchanges communicate with one another to find the least congested alternative route for traffic. Again, there is delay in gathering this information and the system is complex.
U.S. Pat. No. 3,536,842 discloses a telephone network in which a history record is kept of the success or failure of calls extended over a trunk route to each terminating office that is reached via that route. The history record is consulted on subsequent calls, and used to affect decisions as to choice for route for subsequent calls. In the method disclosed in that Patent, the history record is a complex one, which carries information relating to the relative success history of each route to each destination. When a first preferred trunk route fails, the next best trunk route is selected from the history record.
This approach appears attractive at first sight, but in practice results in a need for very substantial processing capability at each node, and the processing overhead involved can lead to a loss of calls in a heavily loaded network.
Further work, largely theoretical, proposes various decentralised routing strategies, referred to as learning automata. In one of the simplest of them, the probabilities of success for a call along each possible path are updated after every call has been processed. If there are r routes from exchange i to exchange j, the r routes will be attempted in a random order with changing probabilities. Many such schemes may be more sophisticated than this. The amount of processing capacity required for these strategies can be relatively large, particularly for the more sophisticated ones.
According to a first aspect of the present invention there is provided a method of routing traffic in a circuit switched network, comprising offering calls between an origin node and a destination node to one or more preferred routes, and if the said preferred routes are not available, offering at least one alternative route, wherein calls are offered to one or more current nominated alternative routes until such route is not available, at which point the said current nominated alternative route is changed.
In accordance with the first aspect of the present invention there is provided a simple and efficient routing scheme in which blocked calls on a first choice route are directed to a current nominated alternative route, the same alternative route being chosen until such route is no longer available. The current nominated alternative route is then changed in a way which is random in the sense that the search technique does not restrict unduly the patterns of routing that can emerge, taking into account the various alternative routes used by different source-destination pairs. In particular, it is desirable that the search technique used should not bias the routing pattern that emerges towards any predefined routing pattern and/or away from any pattern which might under certain network operating conditions be desirable. Thus a choice may be made among the various available alternative routes according to, for example, a stochastic, pseudo random, or cyclic mechanism.
The present invention also provides apparatus for routing traffic through a circuit-switched network comprising processors at respective nodes, each processor being adapted to offer calls at a node to one or more preferred routes and if said preferred routes are not available, offering alternative routes wherein calls are offered to one or more current nominated alternative routes until such route is not available, at which point the said current nominated alternative route is changed.